1. Field of the Invention
This invention relates to a communication network, and the reliable routing of information across the network using lookup tables and content addressable memory. In particular, the present invention relates to an apparatus and method of searching a database having duplicative entries placed into the memory, noting which entry of the duplicative entries is erroneous, and copying a correct entry into the erroneous entry to achieve a more reliable search result. The present apparatus and method can extend to any prioritized set of associative rules applied in parallel, but for which error detection can occur serially.
2. Description of the Related Art
The following descriptions and examples are not admitted to be conventional by virtue of their inclusion within this section.
A communication network is generally recognized as an interconnection of forwarding devices that processes and sends packets of information across the network. One objective of the forwarding devices is to reliably forward the packets from a source to a destination. Thus, the network can either be an Internet or an Intranet and the forwarding devices can be gateways, bridges, switches, or routers.
In whatever form, a forwarding device typically includes one or more lookup tables. An incoming destination address or search key, derived from a packet of information, can be compared to entries stored within the lookup table. Resulting from the search, the associated packet of information may be processed according to a set of rules and sent to an appropriate port of the forwarding device. As links of the network change, routing protocols exchange information among the forwarding devices in order to change the entries within the corresponding lookup tables. This change will modify not only the entries within the lookup table, but also the next-hop identifiers or other associated data pointed to by the addresses of those entries. Routing through the forwarding devices can, therefore, be changed dynamically as links go down and come back up in various parts of the Internet or Intranet.
A popular implementation of the lookup table involves content-addressable memory (CAM). A CAM contains many CAM entries that are searched by a search key. One important feature of a CAM is that fairly fast searches can be undertaken of any database, list, pattern, image, or voice-recognition stored within a computer or a communication network. Contrary to conventional memory devices, CAMs do not store data in any structured fashion. The locations at which data is stored within a CAM can be arbitrary, where the data can be written directly into any location within the CAM. Once data is stored in CAM, that data can be found by comparing every bit within all of the CAM entries with input data placed in a comparand register. If a match exists for the set of values (i.e., binary or ternary bit values, depending on whether the values are bit-maskable) stored in a particular CAM entry, a match line is asserted for that entry. Thus, the match operation can take place within a single entry in a CAM (i.e., in the form of either a binary match, a ternary match, a range-based match such as a greater-than match, or any other kind of logical match function). A CAM thereby operates opposite that of a conventional memory device by receiving data and returning a CAM entry index, address, or location.
When searching in parallel all binary/ternary values (hereinafter, simply “values”) across all CAM entries, multiple match lines might be asserted. The CAM typically includes one or more priority encoders that then translate the highest priority matching CAM index (or location) into a match address that is thereafter forwarded to discrete memory specified by that address. The discrete memory device may then direct the packet of information to the output port identified by that memory.
In order to reliably perform fast parallel searches, and to ensure the forwarding devices can correctly process and forward packets of information, the values stored in each of the CAM entries must not contain errors. Unfortunately, however, errors can occur when writing values into CAM entries. Errors can also occur in entries at any time after they are written. With the advent of smaller geometries and process skews, soft errors due to alpha-particle radiation, cosmic-ray radiation, and on-chip inter-symbol interference are likely to increase. The impact of such errors on normal CAM operation may be large due to the fact that all CAM locations are searched in parallel. A search operation on all CAM entries may provide an erroneous result due to two possible conditions: (i) an entry being searched contains one or more errors causing it to incorrectly match the comparand data (“false-hit” condition); or (ii) an entry being searched contains one or more errors causing it to incorrectly mismatch the comparand data (“false-miss” condition). Such errors can, in most instances, be eliminated by simply rewriting the proper values into an entry having improper values. Such rewriting of erroneous entries may be facilitated in the forwarding device by the intervention of an external central processing unit (CPU). However, before the errors can be fixed, the erroneous entries in the CAM must first be detected. Moreover, the time taken for such detection and correction of erroneous CAM entries by the forwarding device may be sufficiently large such that erroneous CAM entries adversely affect the reliability, correctness, and performance of the forwarding device.
It would be desirable to provide a circuit and method to detect erroneous values within a CAM during a search operation, isolate which entries contain those erroneous values, and then correct those erroneous values during or immediately following the search operation. By performing error detection, identification, and correction as an entry is being searched, one can be assured that the search cannot produce erroneous results, and that the impact to the forwarding device's performance is minimized.